166B - Polygons - CodeForces Solution

// Mihai Priboi

#include <stdio.h>
#include <algorithm>

#define int64 long long

struct point { 
  int x, y;

  bool operator==(const point& a) const {
    return x == a.x && y == a.y;
  }
};

#define INF 1'000'000'000
#define MAX_N 100'000
#define MAX_M 20'000

point v[MAX_N + MAX_M], a[MAX_N];
point start;

int st[MAX_N + MAX_M];
int st_size;

bool cmp(const point& a, const point& b) {
  if(start == a)
    return true;
  return (int64)(a.y - start.y) * (b.x - start.x) < (int64)(b.y - start.y) * (a.x - start.x);
}

bool is_trig(const point& a, const point& b, const point& c) {
  return (int64)(b.y - a.y) * (c.x - a.x) < (int64)(c.y - a.y) * (b.x - a.x);
}

bool is_collinear(const point& a, const point& b, const point& c) {
  return (int64)(b.y - a.y) * (c.x - a.x) == (int64)(c.y - a.y) * (b.x - a.x);
}

int main() {
  FILE *fin, *fout;
  #ifndef ONLINE_JUDGE
    fin = fopen(".in", "r");
    fout = fopen(".out", "w");
    #define DEBUG
  #else
    fin = stdin;
    fout = stdout;
  #endif

  int n, m, i, j;

  start = {INF, INF};

  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++) {
    fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    a[i] = {v[i].x, v[i].y};

    if((v[i].x == start.x && v[i].y < start.y) || v[i].x < start.x)
      start = v[i];
  }
  
  fscanf(fin, "%d", &m);
  for(i = n; i < n + m; i++)
    fscanf(fin, "%d%d", &v[i].x, &v[i].y);

  std::sort(v, v + n + m, cmp);

  #ifdef DEBUG
    for(i = 0; i < n + m; i++)
      printf("%d %d\n", v[i].x, v[i].y);
    printf("\n");
  #endif
  
  // convex hull
  st[0] = 0;
  st[1] = 1;
  st_size = 2;

  for(i = 2; i < n + m; i++) {
    while(st_size > 1 && !is_trig(v[st[st_size - 2]], v[st[st_size - 1]], v[i]))
      st_size--;
    
    st[st_size++] = i;
  }

  #ifdef DEBUG
    for(i = 0; i < st_size; i++)
      printf("%d %d\n", v[st[i]].x, v[st[i]].y);
  #endif

  // checking if the polynom A is the convex hull
  j = 0;
  while(j < n && !(a[j] == v[st[st_size - 1]]))
    j++;

  bool is_a_ch = true;

  // check if there is a point of B on A
  int ind = 0;
  int l, r;
  l = st[ind++];
  r = st[ind++];
  
  for(i = 1; i < n + m; i++) {
    if(l < i && i < r) {
      if(is_collinear(v[l], v[i], v[r]))
        is_a_ch = false;
    }
    else if(r == i) {
      l = r;
      r = st[ind++];
    }
  }

  // if st[size - 1] not found, then A is not the convex hull
  if(j == n)
    is_a_ch = false;
  else {
    i = st_size - 1;
    while(i >= 0 && is_a_ch) {
      if(!(a[j] == v[st[i]]))
        is_a_ch = false;
      
      i--;
      j++;
      if(j == n)
        j = 0;
    }
  }

  if(is_a_ch)
    fprintf(fout, "YES");
  else
    fprintf(fout, "NO");

  return 0;
}